package com.zj.leetcode.medium;

/**
 * @program: algorithm
 * @description:
 * @author: Zhang Bo
 * @create: 2022-01-12 14:17
 **/
public class UniqueSubstringsInWraparoundString {
    public static void main(String[] args) {
//        String p = "zab";
//        String p = "cac";
        String p = "zabzabzab";
        Solution solution = new UniqueSubstringsInWraparoundString().new Solution();
        System.out.println(solution.findSubstringInWraparoundString(p));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int findSubstringInWraparoundString(String p) {
            int left = 0;
            int right = 1;
            int ret = 0;
            if (p.length() <= 1) {
                return p.length();
            }
            int[] barrel = new int[26];

            while (right < p.length()) {
                int sub = p.charAt(left) - p.charAt(right);
                while ((sub == -1 || sub == 25) && right < p.length()) {
                    ++right;
                    sub = p.charAt(left) - p.charAt(right);
                    int count = right - left;
                    barrel[p.charAt(right) - 'a'] = Math.max(barrel[p.charAt(right) - 'a'], count);
                }

                int count = right - left;

                barrel[p.charAt(right) - 'a'] = Math.max(barrel[p.charAt(right) - 'a'], count);

                left = right;
                ++right;
            }

            for(int temp : barrel)
                ret += temp;
            return ret;
        }


        public int findSubstringInWraparoundString02(String p) {
            /**
             统计以每个字符作为结尾的最长连续序列(可以覆盖掉重复的短序列的情况), 他们的和即为所求
             例如:abcdbcd, 对于以d结尾的有abcd, bcd, cd和d, 而bcd产生的序列都会被abcd所覆盖
             总和即以a、b、c和d结尾的所有连续最长序列1 + 2 + 3 + 4 = 10
             **/
            int n = p.length();
            if(n < 1) return 0;
            int ret = 0;
            int[] count = new int[26];
            char[] str = p.toCharArray();
            int curMaxLen = 1;
            for(int i = 0; i < n; ++i) {
                if(i > 0 && (str[i]-str[i-1] == 1 || str[i-1]-str[i] == 25))
                    curMaxLen++;
                else
                    curMaxLen = 1;
                count[str[i]-'a'] = Math.max(count[str[i]-'a'], curMaxLen);
            }
            for(int temp : count)
                ret += temp;
            return ret;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
